package objectRank;

/**
 *
 * @author Reza Amini
 */
import java.io.*;
import java.util.*;

public class QueryGraph implements Serializable {
    // The total number of nodes in the graph

    private int nodeCount;
    // The numbers of users, groups, queries, and documents
    private int userCount;
    private int groupCount;
    private int documentCount;
    private int queryCount;
    // Damping factor
    private final double d = 0.85;
    private final double impFac = 0.5;
    /* Maps storing relationships from users, groups,
     * queries, and documents to numeric Identifyers
     */
    private HashMap<Node, Integer> nodeToIdentifyer;
    private HashMap<String, Integer> userToIdentifyer;
    private HashMap<String, Integer> groupToIdentifyer;
    private HashMap<String, Integer> queryToIdentifyer;
    private HashMap<String, Integer> documentToIdentifyer;
    /* Maps storing relationships from numeric Identifyers to users, groups,
     * queries, and documents
     */
    public HashMap<Integer, Node> identifyerToNode;
    public HashMap<Integer, User> identifyerToUser;
    public HashMap<Integer, Group> identifyerToGroup;
    public HashMap<Integer, Query> identifyerToQuery;
    public HashMap<Integer, Document> identifyerToDocument;
    private HashSet<Node> rootSet;
    private HashSet<Node> baseSet;

    // Constructor for WebGraph
    public QueryGraph() {
        this.nodeToIdentifyer = new HashMap<Node, Integer>();
        this.userToIdentifyer = new HashMap<String, Integer>();
        this.groupToIdentifyer = new HashMap<String, Integer>();
        this.queryToIdentifyer = new HashMap<String, Integer>();
        this.documentToIdentifyer = new HashMap<String, Integer>();
        this.identifyerToNode = new HashMap<Integer, Node>();
        this.identifyerToUser = new HashMap<Integer, User>();
        this.identifyerToGroup = new HashMap<Integer, Group>();
        this.identifyerToQuery = new HashMap<Integer, Query>();
        this.identifyerToDocument = new HashMap<Integer, Document>();
        this.nodeCount = 0;
        this.groupCount = 0;
        this.userCount = 0;
        this.queryCount = 0;
        this.documentCount = 0;
        this.rootSet = new HashSet<Node>();
        this.baseSet = new HashSet<Node>();
    }

    /**
     * Constructor for WebGraph which reads data from a text file. Each line
     * of the file contains an association in the form: 
     * fromNode -> toNode   OR   node
     * Stating that "fromNode" contains an outlink to "toNode". 
     *
     * @param file The name of the file
     * @throws IOException An error occured while reading the file
     * @throws FileNotFoundException An error occured while reading the file
     */
    public QueryGraph(File file) throws IOException, FileNotFoundException {
        this(); // Calls the QueryGraph constructor
        BufferedReader reader = new BufferedReader(new FileReader(file));
        String line;
        while ((line = reader.readLine()) != null) {
            int index = line.indexOf("->");
            if (index == -1) //It is a node, not an edge from a node to another.
            {
                addNode(line.trim());
            } else { //It is an edge from fromNode to toNode.
                String fromNode = line.substring(0, index).trim();
                String toNode = line.substring(index + 2).trim();
                addEdge(fromNode, toNode);
            }
        }
    }

    /**
     *  Adds a node to the graph
     *
     * @param link The link, name, or string associated with the added node
     */
    public Node addNode(String node) {
        String nodeName;
        Node addedNode = new Node();
        if (node.startsWith(">>group>>")) { // The node is a group name
            nodeName = node.substring(9);
            addedNode = addGroup(nodeName.trim());
        } else if (node.startsWith(">>user>>")) { // The node is a user name
            nodeName = node.substring(8);
            addedNode = addUser(nodeName.trim());
        } else if (node.startsWith(">>query>>")) { // The node is a query
            nodeName = node.substring(9);
            addedNode = addQuery(nodeName.trim());
        } else if (node.startsWith(">>document>>")) { // The node is a document
            nodeName = node.substring(12);
            addedNode = addDocument(nodeName.trim());
        } else {
            System.out.println("Wrong input in file!");
            addedNode = null;
        }
        return addedNode;
    }

    /**
     * Adds a Group node to the graph
     *
     * @param groupDescription The description of the group to be added
     */
    private Node addGroup(String groupDescription) {
        Integer id = groupToIdentifyer(groupDescription);
        if (id == null) {
            id = new Integer(++groupCount);
            Integer nodeId = new Integer(++nodeCount);
            groupToIdentifyer.put(groupDescription, id);
            Group group = new Group(groupDescription);
            group.id = id;
            identifyerToGroup.put(id, group);
            nodeToIdentifyer.put((Node)group, nodeId);
            identifyerToNode.put(nodeId, (Node)group);
        }
        return (Node) identifyerToGroup(id);
    }

    /**
     * Adds a User node to the graph
     *
     * @param userName The name of the user to be added
     */
    private Node addUser(String userName) {
        Integer id = userToIdentifyer(userName);
        if (id == null) {
            id = new Integer(++userCount);
            Integer nodeId = new Integer(++nodeCount);
            userToIdentifyer.put(userName, id);
            User user = new User(userName);
            user.id = id;
            identifyerToUser.put(id, user);
            nodeToIdentifyer.put((Node)user, nodeId);
            identifyerToNode.put(nodeId, (Node)user);
        }
        return (Node) identifyerToUser(id);
    }

    /**
     * Adds a Query node to the graph
     *
     * @param query The query to be added
     */
    private Node addQuery(String query) {
        Integer id = queryToIdentifyer(query);
        if (id == null) {
            id = new Integer(++queryCount);
            Integer nodeId = new Integer(++nodeCount);
            queryToIdentifyer.put(query, id);
            Query q = new Query(query);
            q.id = id;
            identifyerToQuery.put(id, q);
            nodeToIdentifyer.put((Node)q, nodeId);
            identifyerToNode.put(nodeId, (Node)q);
        }
        return (Node) identifyerToQuery(id);
    }

    /**
     * Adds a Document node to the graph
     *
     * @param URL The URL of the document to be added
     */
    private Node addDocument(String URL) {
        Integer id = documentToIdentifyer(URL);
        if (id == null) {
            id = new Integer(++documentCount);
            Integer nodeId = new Integer(++nodeCount);
            documentToIdentifyer.put(URL, id);
            Document document = new Document(URL);
            document.id = id;
            identifyerToDocument.put(id, document);
            nodeToIdentifyer.put((Node)document, nodeId);
            identifyerToNode.put(nodeId, (Node)document);
        }
        return (Node) identifyerToDocument(id);
    }

    /**
     * Returns the associated Node object of a node Id
     * @param id The node Id
     * @return The associated Node object
     */
    public Node identifyerToNode(Integer id) {
        return identifyerToNode.get(id);
    }

    /**
     * Returns the associated User object of a user Id
     * @param id The user Id
     * @return The associated User object
     */
    public User identifyerToUser(Integer id) {
        return identifyerToUser.get(id);
    }

    /**
     * Returns the associated Group object of a group Id
     * @param id The group Id
     * @return The associated Group object
     */
    public Group identifyerToGroup(Integer id) {
        return identifyerToGroup.get(id);
    }

    /**
     * Returns the associated Query object of a query Id
     * @param id The query Id
     * @return The associated Query object
     */
    public Query identifyerToQuery(Integer id) {
        return identifyerToQuery.get(id);
    }

    /**
     * Returns the associated Document object of a document Id
     * @param id The document Id
     * @return The associated Document object
     */
    public Document identifyerToDocument(Integer id) {
        return identifyerToDocument.get(id);
    }

    /**
     * Returns the associated node Id of a Node object
     * @param node The Node object
     * @return The associated node Id
     */
    public Integer nodeToIdentifyer(Node node) {
        return nodeToIdentifyer.get(node);
    }

    /**
     * Returns the associated user Id of a User object
     * @param userName The user name of the User object
     * @return The associated user Id
     */
    public Integer userToIdentifyer(String userName) {
        return userToIdentifyer.get(userName);
    }

    /**
     * Returns the associated group Id of a Group object
     * @param groupDescription The group description of the Group object
     * @return The associated group Id
     */
    public Integer groupToIdentifyer(String groupDescription) {
        return groupToIdentifyer.get(groupDescription);
    }

    /**
     * Returns the associated query Id of a Query object
     * @param query The query text of the Query object
     * @return The associated query Id
     */
    public Integer queryToIdentifyer(String query) {
        return queryToIdentifyer.get(query);
    }

    /**
     * Returns the associated document Id of a Document object
     * @param URL The URL of the Document object
     * @return The associated Document Id
     */
    public Integer documentToIdentifyer(String URL) {
        return documentToIdentifyer.get(URL);
    }

    /**
     * Adds an association between two given nodes in the graph. If the
     * corresponding nodes do not exists, this method creates them first. If the
     * connection already exists, the strength value is updated.
     *
     * @param from The document for the source node in the graph
     * @param to The document for the target node in the graph
     * @return The strength associated with the connection
     */
    public void addEdge(String fromNode, String toNode) {
        Node node1 = addNode(fromNode);
        Node node2 = addNode(toNode);
        double weight;
        Integer id1 = null;
        Integer id2 = null;

        if (node1.getClass()==Group.class && node2.getClass()==Group.class) {
            id1 = groupToIdentifyer(((Group)node1).getGroupDescription());
            id2 = groupToIdentifyer(((Group)node2).getGroupDescription());
            weight = weight(node1, node2);
            identifyerToGroup(id1).outLinksToGroups.put(id2, weight);
            identifyerToGroup(id2).inLinksFromGroups.put(id1, weight);

        } else if (node1.getClass()==Group.class && node2.getClass()==User.class) {
            id1 = groupToIdentifyer(((Group)node1).getGroupDescription());
            id2 = userToIdentifyer(((User)node2).getUserName());
            identifyerToGroup(id1).containsUser.put(id2, Boolean.TRUE);
            identifyerToUser(id2).memberOfGroup.put(id1, Boolean.TRUE);
            weight = weight(node1, node2);
            identifyerToGroup(id1).outLinksToUsers.put(id2, weight);
            identifyerToUser(id2).inLinksFromGroups.put(id1, weight);

        } else if (node1.getClass()==Group.class && node2.getClass()==Query.class) {
            id1 = groupToIdentifyer(((Group)node1).getGroupDescription());
            id2 = queryToIdentifyer(((Query)node2).getQuery());
            weight = weight(node1, node2);
            identifyerToGroup(id1).outLinksToQueries.put(id2, weight);
            identifyerToQuery(id2).inLinksFromGroups.put(id1, weight);

        } else if (node1.getClass()==User.class && node2.getClass()==Group.class) {
            id1 = userToIdentifyer(((User)node1).getUserName());
            id2 = groupToIdentifyer(((Group)node2).getGroupDescription());
            identifyerToUser(id1).memberOfGroup.put(id2, Boolean.TRUE);
            identifyerToGroup(id2).containsUser.put(id1, Boolean.TRUE);
            weight = weight(node1, node2);
            identifyerToUser(id1).outLinksToGroups.put(id2, weight);
            identifyerToGroup(id2).inLinksFromUsers.put(id1, weight);

        } else if (node1.getClass()==User.class && node2.getClass()==Query.class) {
            id1 = userToIdentifyer(((User)node1).getUserName());
            id2 = queryToIdentifyer(((Query)node2).getQuery());
            Integer numClicks = identifyerToUser(id1).submitsQuery.get(id2);
            identifyerToUser(id1).submitsQuery.put(id2, (numClicks == null) ? 1 : numClicks + 1);
            numClicks = identifyerToQuery(id2).submittedByUser.get(id1);
            identifyerToQuery(id2).submittedByUser.put(id1, (numClicks == null) ? 1 : numClicks + 1);
            weight = weight(node1, node2);
            identifyerToUser(id1).outLinksToQueries.put(id2, weight);
            identifyerToQuery(id2).inLinksFromUsers.put(id1, weight);

        } else if (node1.getClass()==User.class && node2.getClass()==Document.class) {
            id1 = userToIdentifyer(((User)node1).getUserName());
            id2 = documentToIdentifyer(((Document)node2).getURL());
            Integer numClicks = identifyerToUser(id1).clicksDocument.get(id2);
            identifyerToUser(id1).clicksDocument.put(id2, (numClicks == null) ? 1 : numClicks + 1);
            numClicks = identifyerToDocument(id2).clickedByUser.get(id1);
            identifyerToDocument(id2).clickedByUser.put(id1, (numClicks == null) ? 1 : numClicks + 1);
            weight = weight(node1, node2);
            identifyerToUser(id1).outLinksToDocuments.put(id2, weight);
            identifyerToDocument(id2).inLinksFromUsers.put(id1, weight);

        } else if (node1.getClass()==Query.class && node2.getClass()==User.class) {
            id1 = queryToIdentifyer(((Query)node1).getQuery());
            id2 = userToIdentifyer(((User)node2).getUserName());
            Integer numSubmissions = identifyerToQuery(id1).submittedByUser.get(id2);
            identifyerToQuery(id1).submittedByUser.put(id2, (numSubmissions == null) ? 1 : numSubmissions + 1);
            numSubmissions = identifyerToUser(id2).submitsQuery.get(id1);
            identifyerToUser(id2).submitsQuery.put(id1, (numSubmissions == null) ? 1 : numSubmissions + 1);
            weight = weight(node1, node2);
            identifyerToQuery(id1).outLinksToUsers.put(id2, weight);
            identifyerToUser(id2).inLinksFromQueries.put(id1, weight);

        } else if (node1.getClass()==Query.class && node2.getClass()==Group.class) {
            id1 = queryToIdentifyer(((Query)node1).getQuery());
            id2 = groupToIdentifyer(((Group)node2).getGroupDescription());
            weight = weight(node1, node2);
            identifyerToQuery(id1).outLinksToGroups.put(id2, weight);
            identifyerToGroup(id2).inLinksFromQueries.put(id1, weight);

        } else if (node1.getClass()==Query.class && node2.getClass()==Query.class) {
            id1 = queryToIdentifyer(((Query)node1).getQuery());
            id2 = queryToIdentifyer(((Query)node2).getQuery());
            weight = weight(node1, node2);
            identifyerToQuery(id1).outLinksToQueries.put(id2, weight);
            identifyerToGroup(id2).inLinksFromQueries.put(id1, weight);

        } else if (node1.getClass()==Query.class && node2.getClass()==Document.class) {
            id1 = queryToIdentifyer(((Query)node1).getQuery());
            id2 = documentToIdentifyer(((Document)node2).getURL());
            Integer numDisplays = identifyerToQuery(id1).displayDocument.get(id2);
            identifyerToQuery(id1).displayDocument.put(id2, (numDisplays == null) ? 1 : numDisplays + 1);
            numDisplays = identifyerToDocument(id2).displayedAfterQuery.get(id1);
            identifyerToDocument(id2).displayedAfterQuery.put(id1, (numDisplays == null) ? 1 : numDisplays + 1);
            weight = weight(node1, node2);
            identifyerToQuery(id1).outLinksToDocuments.put(id2, weight);
            identifyerToDocument(id2).inLinksFromQueries.put(id1, weight);

        } else if (node1.getClass()==Document.class && node2.getClass()==User.class) {
            id1 = documentToIdentifyer(((Document)node1).getURL());
            id2 = userToIdentifyer(((User)node2).getUserName());
            Integer numClicks = identifyerToDocument(id1).clickedByUser.get(id2);
            identifyerToDocument(id1).clickedByUser.put(id2, (numClicks == null) ? 1 : numClicks + 1);
            numClicks = identifyerToUser(id2).clicksDocument.get(id1);
            identifyerToUser(id2).clicksDocument.put(id1, (numClicks == null) ? 1 : numClicks + 1);
            weight = weight(node1, node2);
            identifyerToDocument(id1).outLinksToUsers.put(id2, weight);
            identifyerToUser(id2).inLinksFromDocuments.put(id1, weight);

        } else if (node1.getClass()==Document.class && node2.getClass()==Query.class) {
            id1 = documentToIdentifyer(((Document)node1).getURL());
            id2 = queryToIdentifyer(((Query)node2).getQuery());
            Integer numDisplays = identifyerToDocument(id1).displayedAfterQuery.get(id2);
            identifyerToDocument(id1).displayedAfterQuery.put(id2, (numDisplays == null) ? 1 : numDisplays + 1);
            Integer numDisplays2 = identifyerToQuery(id2).displayDocument.get(id1);
            identifyerToQuery(id2).displayDocument.put(id1, (numDisplays2 == null) ? 1 : numDisplays2 + 1);
            weight = weight(node1, node2);
            identifyerToDocument(id1).outLinksToQueries.put(id2, weight);
            identifyerToQuery(id2).inLinksFromDocuments.put(id1, weight);

        } else {
            System.out.println("Wrong input to the addEdge!");
        }
    }

    private double weight(Node node1, Node node2) {
        if (node1.getClass() == User.class) {
            if (node2.getClass() == Group.class) {
                Integer groupId = groupToIdentifyer(((Group) node2).getGroupDescription());
                if (((User) node1).memberOfGroup.get(groupId)) return 1.0; else return 0.0;
            }else if (node2.getClass() == Query.class) {
                Integer queryId = queryToIdentifyer(((Query) node2).getQuery());
                Integer numQuerySubmission = ((User) node1).submitsQuery.get(queryId);
                Collection<Integer> values = ((User) node1).submitsQuery.values();
                Iterator<Integer> valuesIter = values.iterator();
                double numQuery = 0, totalQueryByUser = 0;
                while (valuesIter.hasNext()) {
                    totalQueryByUser =+ valuesIter.next();
                    numQuery = new Double(numQuery++);
                }
                return numQuerySubmission / (totalQueryByUser / numQuery);
            }else if (node2.getClass() == Document.class) {
                Integer docId = documentToIdentifyer(((Document) node2).getURL());
                Integer numDocClick = ((User) node1).clicksDocument.get(docId);
                Set<Integer> keySet = ((User) node1).clicksDocument.keySet();
                Iterator<Integer> keySetIter = keySet.iterator();
                double numDoc = 0, totalClickByUser = 0;
                while (keySetIter.hasNext()) {
                    totalClickByUser =+ keySetIter.next();
                    numDoc = new Double(numDoc++);
                }
                return numDocClick / (totalClickByUser / numDoc);
            }else return -1; //ERROR = -1
        }else if (node1.getClass() == Group.class) {
            if (node2.getClass() == Group.class) {
                return similarity(node1, node2);
            }else if (node2.getClass() == User.class) {
                Integer userId = userToIdentifyer(((User) node2).getUserName());
                if (((Group) node1).containsUser.get(userId) == Boolean.TRUE) return 1; else return 0;
            }else if (node2.getClass() == Query.class) {
                return similarity(node1, node2);
            }else return -1; //ERROR = -1
        }else if (node1.getClass() == Query.class) {
            if (node2.getClass() == Group.class) {
                return similarity(node1, node2);
            }else if (node2.getClass() == User.class) {
                Integer userId = userToIdentifyer(((User) node2).getUserName());
                Integer numQuerySubmitted = ((Query) node1).submittedByUser.get(userId);
                Set<Integer> keySet = ((Query) node1).submittedByUser.keySet();
                Iterator<Integer> keySetIter = keySet.iterator();
                double numSubmission = 0, totalSubmissionByUsers = 0;
                while (keySetIter.hasNext()) {
                    totalSubmissionByUsers =+ keySetIter.next();
                    numSubmission = new Double(numSubmission++);
                }
                return (double)numQuerySubmitted / (totalSubmissionByUsers / numSubmission);
            }else if (node2.getClass() == Query.class) {
                return similarity(node1, node2);
            }else if (node2.getClass() == Document.class) {
                Integer docId = documentToIdentifyer(((Document) node2).getURL());
                Integer queryId = queryToIdentifyer(((Query) node1).getQuery());
                Integer numDocDisplay = ((Document) node2).displayedAfterQuery.get(queryId);
                Integer numClicksAfterQuery = ((Document) node2).clickedAfterQuery.get(queryId);
                if(numClicksAfterQuery == null) numClicksAfterQuery = 0;
                if(numDocDisplay == null) return 0;
                return ((double)numClicksAfterQuery / numDocDisplay);
            }else return -1; //ERROR = -1
        }else if (node1.getClass() == Document.class) {
            if (node2.getClass() == User.class) {
                Integer userId = userToIdentifyer(((User) node2).getUserName());
                Integer numClick = ((Document) node1).clickedByUser.get(userId);
                Set<Integer> keySet = ((Document) node1).clickedByUser.keySet();
                Iterator<Integer> keySetIter = keySet.iterator();
                double numUser = 0, totalClicks = 0;
                while (keySetIter.hasNext()) {
                    totalClicks =+ keySetIter.next();
                    numUser = new Double(numUser++);
                }
                return numClick / (totalClicks / numUser);
            }else if (node2.getClass() == Query.class) {
                Integer docId = documentToIdentifyer(((Document) node1).getURL());
                Integer queryId = queryToIdentifyer(((Query) node2).getQuery());
                Integer numDocDisplay = ((Document) node1).displayedAfterQuery.get(docId);
                Integer numClicksAfterQuery = ((Document) node1).clickedAfterQuery.get(docId);
                System.out.println(numDocDisplay);
                System.out.println(numClicksAfterQuery);
                if(numClicksAfterQuery == null) numClicksAfterQuery = 0;
                if (numDocDisplay == null) return 0.0;
                return ((double)numClicksAfterQuery / numDocDisplay);
            }else return -1; //ERROR = -1
        }else return -1; // ERROR = -1
    }

    /**
     * Calculates the OutDegree of a specific type for a User node
     * 
     * @param user The user node which we want the OutDegree of
     * @param edgeType The type of out going edges
     * @return The OutDegree of the node
     */
    private int outDegree(Node node, Node edgeType) {
        if (node.getClass() == User.class) {
            if (edgeType.getClass() == Group.class && !(node.outLinksToGroups.isEmpty())) {
                return node.outLinksToGroups.keySet().size();
            } else if (edgeType.getClass() == Query.class && !(node.outLinksToQueries.isEmpty())) {
                return node.outLinksToQueries.keySet().size();
            } else if (edgeType.getClass() == Document.class && !(node.outLinksToDocuments.isEmpty())) {
                return node.outLinksToDocuments.keySet().size();
            } else {
                return -1; //ERROR = -1
            }
        } else if (node.getClass() == Group.class) {
            if (edgeType.getClass() == Group.class && !(node.outLinksToGroups.isEmpty())) {
                return node.outLinksToGroups.keySet().size();
            } else if (edgeType.getClass() == User.class && !(node.outLinksToUsers.isEmpty())) {
                return node.outLinksToUsers.keySet().size();
            } else if (edgeType.getClass() == Query.class && !(node.outLinksToQueries.isEmpty())) {
                return node.outLinksToQueries.keySet().size();
            } else {
                return -1; //ERROR = -1
            }
        } else if (node.getClass() == Query.class) {
            if (edgeType.getClass() == Group.class && !(node.outLinksToGroups.isEmpty())) {
                return node.outLinksToGroups.keySet().size();
            } else if (edgeType.getClass() == User.class && !(node.outLinksToUsers.isEmpty())) {
                return node.outLinksToUsers.keySet().size();
            } else if (edgeType.getClass() == Query.class && !(node.outLinksToQueries.isEmpty())) {
                return node.outLinksToQueries.keySet().size();
            } else if (edgeType.getClass() == Document.class && !(node.outLinksToDocuments.isEmpty())) {
                return node.outLinksToDocuments.keySet().size();
            } else {
                return -1; //ERROR = -1
            }
        } else if (node.getClass() == Document.class) {
            if (edgeType.getClass() == User.class && !(node.outLinksToUsers.isEmpty())) {
                return node.outLinksToUsers.keySet().size();
            } else if (edgeType.getClass() == Query.class && !(node.outLinksToQueries.isEmpty())) {
                return node.outLinksToQueries.keySet().size();
            } else {
                return -1; //ERROR = -1
            }
        } else {
            return -1; // ERROR = -1
        }
    }

    /**
     * Returns the authority transfer rate of node type node1 to node type node2
     * as a double number.
     *
     * @param node1 Type of the starting node.
     * @param node2 Type of the ending node.
     * @return The authority transfer rate.
     */
    private double authorityTransferRate(Node node1, Node node2) {
        if ((node1.getClass() == User.class) && (node2.getClass() == Group.class)) {
            return 1;
        }
        if (node1.getClass() == User.class && node2.getClass() == Document.class) {
            return 1;
        }
        if (node1.getClass() == User.class && node2.getClass() == Query.class) {
            return 1;
        }
        if (node1.getClass() == Group.class && node2.getClass() == Group.class) {
            return 1;
        }
        if (node1.getClass() == Group.class && node2.getClass() == User.class) {
            return 1;
        }
        if (node1.getClass() == Group.class && node2.getClass() == Query.class) {
            return 1;
        }
        if (node1.getClass() == Query.class && node2.getClass() == Group.class) {
            return 1;
        }
        if (node1.getClass() == Query.class && node2.getClass() == User.class) {
            return 1;
        }
        if (node1.getClass() == Query.class && node2.getClass() == Query.class) {
            return 1;
        }
        if (node1.getClass() == Query.class && node2.getClass() == Document.class) {
            return 1;
        }
        if (node1.getClass() == Document.class && node2.getClass() == User.class) {
            return 1;
        }
        if (node1.getClass() == Document.class && node2.getClass() == Query.class) {
            return 1;
        } else {
            return 0;
        }
    }

    /**
     * Computes the alfa of the edge e: u -> v
     *
     * @param node1 The starting node
     * @param node2 The ending node which shows the type of the edge
     * @param authorityTransferRate The authority transfer rate of this type of edge
     * @return The alfa of the edge
     */
    private double alfa(Node node1, Node node2) {
        if (outDegree(node1, node2) == 0){
            return 0.0;
        }else{
            return authorityTransferRate(node1, node2) / outDegree(node1, node2);
        }
    }


    public void calculateRootSet(Query query) {
        Iterator<Integer> groupKeyIter = identifyerToGroup.keySet().iterator();
        Iterator<Integer> queryKeyIter = identifyerToQuery.keySet().iterator();
        Integer a = null;
        while (queryKeyIter.hasNext()) {
            a = queryKeyIter.next();
            if (similarity(identifyerToQuery(a), query) > 0) {
                rootSet.add((Node) identifyerToQuery(a));
            }
        }
        while (groupKeyIter.hasNext()) {
            a = groupKeyIter.next();
            if (similarity(identifyerToGroup(a), query) > 0) {
                rootSet.add((Node) identifyerToGroup(a));
            }
        }
    }

    public void calculateBaseSet() {
        Iterator<Node> iter = rootSet.iterator();
        Node node = null;
        baseSet.addAll(rootSet);
        while (iter.hasNext()) {
            node = iter.next();
            Set<Integer> inLinks = null;
            Set<Integer> outLinks = null;
            if (node.inLinksFromUsers != null)
                inLinks = node.inLinksFromUsers.keySet();
                for (Integer inLink : inLinks) baseSet.add((Node) identifyerToUser(inLink));
            if (node.outLinksToUsers != null)
                outLinks = node.outLinksToUsers.keySet();
                for (Integer outLink : outLinks) baseSet.add((Node) identifyerToUser(outLink));

            if (node.inLinksFromGroups != null)
                inLinks = node.inLinksFromGroups.keySet();
                for (Integer inLink : inLinks) baseSet.add((Node) identifyerToGroup(inLink));
            if (node.outLinksToGroups != null)
                outLinks = node.outLinksToGroups.keySet();
                for (Integer outLink : outLinks) baseSet.add((Node) identifyerToGroup(outLink));
                        
            if (node.inLinksFromQueries != null)
                inLinks = node.inLinksFromQueries.keySet();
                for (Integer inLink : inLinks) baseSet.add((Node) identifyerToQuery(inLink));
            if (node.outLinksToQueries != null)
                outLinks = node.outLinksToQueries.keySet();
                for (Integer inLink : inLinks) baseSet.add((Node) identifyerToQuery(inLink));

            if (node.inLinksFromDocuments != null)
                inLinks = node.inLinksFromDocuments.keySet();
                for (Integer inLink : inLinks) baseSet.add((Node) identifyerToDocument(inLink));
            if (node.outLinksToDocuments != null)
                outLinks = node.outLinksToDocuments.keySet();
                for (Integer outLink : outLinks) baseSet.add((Node) identifyerToDocument(outLink));
        }
    }

    private double similarity(Node node1, Node node2) {
        String delimiters = "\\s*[. ,+*?!%$]\\s*";
        int numCommon = 0;
        String[] tokens1 = null;
        String[] tokens2 = null;
        HashMap node1Map = new HashMap();
        HashMap node2Map = new HashMap();

        if (node1.getClass() == Query.class) {
            tokens1 = ((Query) node1).getQuery().split(delimiters);
        } else if (node1.getClass() == Group.class) {
            tokens1 = ((Group) node1).getGroupDescription().split(delimiters);
        } else {
            System.out.println("Wrong input is passed to similarity method.");
        }

        if (node2.getClass() == Query.class) {
            tokens2 = ((Query) node2).getQuery().split(delimiters);
        } else if (node2.getClass() == Group.class) {
            tokens2 = ((Group) node2).getGroupDescription().split(delimiters);
        } else {
            System.out.println("Wrong input is passed to similarity method.");
        }

        for (String token1 : tokens1) {
            node1Map.put(token1, null);
        }
        for (String token2 : tokens2) {
            node2Map.put(token2, null);
        }
        Iterator<Integer> tokIter = node1Map.keySet().iterator();
        while (tokIter.hasNext()) {
            if (node2Map.containsKey(tokIter.next())) {
                numCommon++;
            }
        }
        return (double) numCommon / (node1Map.size() + node2Map.size() - numCommon);
    }


    public HashMap<Node, Double> calculateObjectRank() {
        //int baseSetCount = baseSet.size();
        HashMap<Node, Double> currentRank = new HashMap<Node, Double>();
        HashMap<Node, Double> resultRank = new HashMap<Node, Double>();
        double difference = 0;
        Node tempNode = null;
        Iterator<Node> iter = nodeToIdentifyer.keySet().iterator();
        while (iter.hasNext()) {
            tempNode = iter.next();
            currentRank.put(tempNode, 1.0 / nodeCount);
            resultRank.put(tempNode, (1.0 - d) / nodeCount);
            difference =+ Math.pow(currentRank.get(tempNode) - resultRank.get(tempNode), 2);
        }
        double threshold = Math.sqrt(difference);
        double rank = 0;
        Node x = null;
        while (threshold > 0.001) {
            iter = nodeToIdentifyer.keySet().iterator();
            while (iter.hasNext()) {
                rank = 0;
                x = iter.next();
                if ((x.getClass()!= User.class) && !((x.inLinksFromUsers).isEmpty())){
                    Iterator<Integer> userIter = x.inLinksFromUsers.keySet().iterator();
                    int e = 0;
                    while (userIter.hasNext()) {
                        Integer userId = userIter.next();
                        Node y = (Node) identifyerToUser(userId);
                        e = (baseSet.contains(y))? 1 : 0;
                        if (x.inLinksFromUsers.containsKey(userId)){
                            double w = x.inLinksFromUsers.get(userId);
                            rank =+ (w * alfa(y, x) * currentRank.get(y));
                        }
                    }
                    rank = rank * d + (1 - d) * e;
                }

                if ((x.getClass()!= Document.class) && !((x.inLinksFromGroups).isEmpty())){
                    Iterator<Integer> groupIter = x.inLinksFromGroups.keySet().iterator();
                    int e = 0;
                    while (groupIter.hasNext()) {
                        Integer groupId = groupIter.next();
                        Node y = (Node) identifyerToGroup(groupId);
                        e = (baseSet.contains(y))? 1 : 0;
                        if (x.inLinksFromGroups.containsKey(groupId)){
                            double w = x.inLinksFromGroups.get(groupId);
                            rank =+ (w * alfa(y, x) * currentRank.get(y));
                        }
                    }
                    rank = rank * d + (1 - d) * e;
                }
                
                if (!((x.inLinksFromQueries).isEmpty())){
                    Iterator<Integer> queryIter = x.inLinksFromQueries.keySet().iterator();
                    int e = 0;
                    while (queryIter.hasNext()) {
                        Integer queryId = queryIter.next();
                        Node y = (Node) identifyerToQuery(queryId);
                        e = (baseSet.contains(y))? 1 : 0;
                        if (x.inLinksFromQueries.containsKey(queryId)){
                            double w = x.inLinksFromQueries.get(queryId);
                            rank =+ (w * alfa(y, x) * currentRank.get(y));
                        }
                    }
                    rank = rank * d + (1 - d) * e;
                }
                
                if ((x.getClass()!= Group.class) && (x.getClass()!= Document.class) && !((x.inLinksFromDocuments).isEmpty())){
                    Iterator<Integer> documentIter = x.inLinksFromDocuments.keySet().iterator();
                    int e = 0;
                    while (documentIter.hasNext()) {
                        Integer documentId = documentIter.next();
                        Node y = (Node) identifyerToDocument(documentId);
                        e = (baseSet.contains(y))? 1 : 0;
                        if (x.inLinksFromDocuments.containsKey(documentId)){
                            double w = x.inLinksFromDocuments.get(documentId);
                            /*System.out.println(w + "," + authorityTransferRate(y, x) + "," +
                                outDegree(y, x) + "," + currentRank.get(y) + "," +
                                e);*/
                            rank =+ (w * alfa(y, x) * currentRank.get(y));
                        }
                    }
                    rank = rank * d + (1 - d) * e;
                }
                resultRank.put(x, rank);
            }
            iter = nodeToIdentifyer.keySet().iterator();
            difference = 0;
            while (iter.hasNext()) {
                tempNode = iter.next();
                difference =+ Math.pow(currentRank.get(tempNode) - resultRank.get(tempNode), 2);
            }
            threshold = Math.sqrt(difference);
            currentRank = resultRank;
        }
        return resultRank;
    }

    public static LinkedHashMap<Node, Double> sortHashMapByValues(HashMap<Node, Double> passedMap) {
        List<Node> mapKeys = new ArrayList(passedMap.keySet());
        List<Double> mapValues = new ArrayList(passedMap.values());
        Collections.sort(mapValues);
        Collections.reverse(mapValues);
        LinkedHashMap<Node, Double> sortedMap = new LinkedHashMap<Node, Double>();
        Iterator<Double> valueItr = mapValues.iterator();
        while (valueItr.hasNext()) {
            Double val = valueItr.next();
            Iterator<Node> keyItr = mapKeys.iterator();
            while (keyItr.hasNext()) {
                Node key = keyItr.next();
                Double comp = passedMap.get(key);
                if (comp == val){
                    sortedMap.put(key, val);
                    passedMap.remove(key);
                    mapKeys.remove(key);
                    break;
                }
            }
        }
        return sortedMap;
    }

    public LinkedHashMap<GoogleDocument, Double> integrateWithGoogle(
            HashMap<Node, Double> objectRanks, LinkedList<GoogleDocument> googleOutput){
        Iterator<Node> nodeItr = objectRanks.keySet().iterator();
        HashMap<Node, Double> tempObjRanks = new HashMap<Node, Double>();
        while(nodeItr.hasNext()){
            Node nextNode = nodeItr.next();
            if (nextNode.getClass()== Document.class){
                tempObjRanks.put(nextNode, objectRanks.get(nextNode));
            }
        }
        LinkedHashMap<Node, Double> rankedNodes = sortHashMapByValues(tempObjRanks);
        nodeItr = rankedNodes.keySet().iterator();
        LinkedHashMap<Document, Double> documentRanks = new LinkedHashMap<Document, Double>();
        while(nodeItr.hasNext()){
            Node tempNode = nodeItr.next();
            Document doc = ((Document)tempNode);
            documentRanks.put(doc, rankedNodes.get(tempNode));
        }
        
        double s1 = Collections.min(documentRanks.values());
        double sn = Collections.max(documentRanks.values());
        int n = documentRanks.size();
        double step = (s1+sn)/n;

        Iterator<GoogleDocument> itr = googleOutput.iterator();
        LinkedHashMap<GoogleDocument, Double> googleScoredOutput = new LinkedHashMap<GoogleDocument, Double>();
        for(int i = 0 ; i < googleOutput.size() ; i++){
            googleScoredOutput.put(itr.next(), step*(i+1));
        }

        LinkedHashMap<GoogleDocument, Double> finalOutput = new LinkedHashMap<GoogleDocument, Double>();
        Iterator<GoogleDocument> itr1 = googleScoredOutput.keySet().iterator();
        GoogleDocument doc;
        Iterator<Document> itr2;
        while(itr1.hasNext()){
            doc = itr1.next();
            String url = doc.getURL();
            itr2 = documentRanks.keySet().iterator();
            Document dd;
            finalOutput.put(doc, (1-impFac)*googleScoredOutput.get(doc));
            while(itr2.hasNext()){
                dd = itr2.next();
                if(dd.getURL().equalsIgnoreCase(url)){
                    finalOutput.put(doc,
                        impFac*documentRanks.get(dd) + (1-impFac)*googleScoredOutput.get(doc));
                    break;
                }
            }
        }
        itr2 = documentRanks.keySet().iterator();
        Document dd;
        while(itr2.hasNext()){
            dd = itr2.next();
            String url = dd.getURL();
            itr1 = googleScoredOutput.keySet().iterator();
            GoogleDocument gd;
            while(itr1.hasNext()){
                gd = itr1.next();
                if (!(gd.getURL().equals(url))){
                    finalOutput.put(gd, impFac*documentRanks.get(dd));
                }
            }
        }
        return finalOutput;
    }
}
